Aller au contenu principal

File, Pile et ArrayDeque

La File (Queue) — FIFO​

Une file fonctionne selon le principe FIFO : First In, First Out — le premier élément ajouté est le premier à être retiré.

Pense à une file d'attente à la caisse : la première personne arrivée est la première servie. Personne ne peut "couper" la file.

Entrée →  [ 3 | 2 | 1 ]  → Sortie
           ↑                 ↑
        addLast()        removeFirst()

Quand l'utiliser ?

  • Traitement de tâches dans l'ordre d'arrivée (impression, requêtes réseau)
  • Algorithmes de parcours en largeur (BFS)
  • Systèmes de messages ou d'événements

BFS (Breadth-First Search) — parcours en largeur :

C'est un algorithme qui explore un graphe ou un arbre niveau par niveau à partir d'un point de départ. Concrètement, imagine chercher la sortie d'un labyrinthe en explorant toutes les directions en même temps, un pas à la fois — ça garantit de trouver le chemin le plus court.

        A          ← Niveau 0 (départ)
       / \
      B   C        ← Niveau 1
     / \
    D   E          ← Niveau 2

Ordre de visite : A → B → C → D → E

La file est essentielle ici : on ajoute les voisins à la fin (addLast) et on traite toujours depuis le début (removeFirst), ce qui garantit qu'on termine un niveau entier avant de passer au suivant.

Exemple — File d'impression :

ArrayDeque<String> fileImpression = new ArrayDeque<>();

// Trois documents envoyés à l'imprimante
fileImpression.addLast("Document A");
fileImpression.addLast("Document B");
fileImpression.addLast("Document C");

// L'imprimante traite dans l'ordre d'arrivée
while (!fileImpression.isEmpty()) {
    System.out.println("Impression : " + fileImpression.removeFirst());
}
// Impression : Document A
// Impression : Document B
// Impression : Document C

La Pile (Stack) — LIFO​

Une pile fonctionne selon le principe LIFO : Last In, First Out — le dernier élément ajouté est le premier à être retiré.

Pense à une pile d'assiettes : on pose une assiette par-dessus les autres, et on reprend toujours celle du dessus.

        ┌───┐  ← push() / addFirst()
        │ 3 │  ← sommet (dernier ajouté)
        │ 2 │
        │ 1 │
        └───┘  ← pop() / removeFirst() retire aussi depuis le sommet

Quand l'utiliser ?

  • Navigation "retour en arrière" (historique de navigateur, Undo/Redo)
  • Évaluation d'expressions mathématiques
  • Appels de fonctions récursives (la JVM utilise elle-même une pile d'appels)

Exemple — Historique de navigation :

ArrayDeque<String> historique = new ArrayDeque<>();

// L'utilisateur visite des pages
historique.push("google.com");
historique.push("github.com");
historique.push("stackoverflow.com");

// L'utilisateur appuie sur "retour" trois fois
while (!historique.isEmpty()) {
    System.out.println("Retour vers : " + historique.pop());
}
// Retour vers : stackoverflow.com  ← dernière page visitée, première retournée
// Retour vers : github.com
// Retour vers : google.com

ArrayDeque — 2 pour 1​

ArrayDeque est une implémentation de la classe Deque en Java qui repose sur un tableau dynamique. Elle fait partie du package java.util et est souvent utilisée comme une alternative plus performante à LinkedList pour les opérations de file (queue) et de pile (stack).

Caractéristiques principales :​

  1. Double extrémité : Permet d’ajouter et de supprimer des éléments à la fois au début et à la fin.
  2. Performances optimisées : Contrairement à LinkedList, elle évite la surcharge de gestion des noeuds chaînés et offre des opérations O(1) pour addFirst(), addLast(), removeFirst() et removeLast().
  3. Pas de capacité fixe : Elle s’agrandit dynamiquement en doublant sa taille lorsque nécessaire.
  4. Non synchronisée : Elle n'est pas thread-safe, donc il faut la synchroniser manuellement en cas d'utilisation concurrente.

Principales méthodes :​

  • Ajout d’éléments : 
    deque.addFirst(10); // Ajoute en tête
    deque.addLast(20);  // Ajoute en queue
    deque.offerFirst(30); // Ajoute en tête sans exception si la capacité est atteinte
    deque.offerLast(40);  // Ajoute en queue sans exception
  • Suppression d’éléments : 
    deque.removeFirst(); // Supprime et retourne le premier élément
    deque.removeLast();  // Supprime et retourne le dernier élément
    deque.pollFirst(); // Supprime et retourne le premier élément, ou null si vide
    deque.pollLast();  // Supprime et retourne le dernier élément, ou null si vide
  • Accès sans suppression : 
    deque.getFirst(); // Retourne le premier élément sans le supprimer
    deque.getLast();  // Retourne le dernier élément sans le supprimer
    deque.peekFirst(); // Pareil que getFirst() mais retourne null si vide
    deque.peekLast();  // Pareil que getLast() mais retourne null si vide
  • Utilisation comme pile (LIFO) : 
    deque.push(50); // Ajoute en haut de la pile
    deque.pop();    // Retire et retourne l'élément du haut de la pile
  • Autres : 
    deque.size();       // Retourne la taille de la deque
    deque.isEmpty();    // Vérifie si elle est vide
    deque.clear();      // Vide la deque

Exemple d’utilisation :​

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();

        deque.addFirst(1);
        deque.addLast(2);
        deque.addLast(3);

        System.out.println(deque); // [1, 2, 3]

        System.out.println(deque.removeFirst()); // 1
        System.out.println(deque.removeLast());  // 3

        System.out.println(deque); // [2]
    }
}

Complexité des opérations​

OpérationFile (FIFO)Pile (LIFO)Deque
Ajout (addLast / push / addFirst)O(1) amortieO(1) amortieO(1) amortie
Suppression (removeFirst / pop / removeLast)O(1)O(1)O(1)
Accès au sommet/tête (getFirst / getLast)O(1)O(1)O(1)
Recherche (contains)O(n)O(n)O(n)
Taille (size)O(1)O(1)O(1)

Quand utiliser ArrayDeque ?​

  • Lorsqu'on a besoin d'une pile (LIFO) ou d'une file à double extrémité (FIFO) performante.
  • Lorsqu'on veut éviter la surcharge mémoire et la complexité d'un LinkedList.
  • Quand on veut une alternative plus efficace que Stack pour une pile.

ArrayDeque est particulièrement utile lorsqu'on a besoin d'une structure de données performante pour gérer des éléments de manière dynamique, avec des accès rapides aux extrémités. Voici quelques scénarios concrets où elle vaut la peine d’être utilisée :

1. Système de gestion des tâches (Scheduler)​

Cas d’usage : Une application qui gère une file de tâches à traiter, avec la possibilité d'ajouter des tâches en priorité (au début) ou en arrière-plan (à la fin).

2. Parcours en largeur d'un graphe (BFS)​

Cas d’usage : Algorithme de recherche pour trouver le chemin le plus court dans un labyrinthe ou une carte.

3. Implémentation d'un "Undo/Redo"​

Cas d’usage : Un éditeur de texte qui doit gérer l’annulation et la réapplication des actions de l’utilisateur.

4. Traitement des requêtes dans un serveur​

Cas d’usage : Un serveur web qui gère les requêtes entrantes en mode FIFO — la première requête reçue est la première traitée.

Pourquoi ArrayDeque ?

  • addLast() / removeFirst() simulent parfaitement une file.
  • Plus performant que LinkedList pour ce type d’accès séquentiel.